package org.atovio.structure.tree;

/**
 * 三叉链表存储的二叉树类，实现先序/中序遍历
 *
 * @author AtoVio, Winter Yuan
 * @version 1.0
 */
public class TriBinaryTree<T> {

    // 根结点
    public TriNode<T> root;

    // 构造空树
    public TriBinaryTree() {
        this.root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 中序遍历
     */
    public void inOrder() {
        System.out.print("(");
        // 寻找第一个访问结点
        TriNode<T> p = this.infixFirst(this.root);
        if (p != null) {
            System.out.print(p.data);
            // 获取下一个要访问的结点
            p = infixNext(p);
        }
        for (; p != null; p = this.infixNext(p))
            System.out.print(", " + p.data);
        System.out.println(")");
    }

    /**
     * 寻找以p为根结点的子树的最小叶子结点
     *
     * @param p 子树的根结点
     * @return 最小的叶子结点
     */
    public TriNode<T> infixFirst(TriNode<T> p) {
        if (p != null)
            // 寻找最小的叶子结点
            while (p.left != null)
                p = p.left;
        return p;
    }

    /**
     * 寻找结点p的下一个访问结点
     *
     * @param p 当前访问的结点
     * @return 下一个访问的结点
     */
    public TriNode<T> infixNext(TriNode<T> p) {
        if (p != null) {
            // 如果p有右孩子，则从右子树找待访问结点
            if (p.right != null)
                return infixFirst(p.right);
            // p没有右孩子,往上寻找某个祖先结点
            while (p.parent != null) {
                // 若p是父结点的左节点，则访问的后继结点为该父结点
                if (p.parent.left == p)
                    return p.parent;
                p = p.parent;
            }
        }
        return null;
    }

}
